package com.yanceysong.codetop.s71_s80;

public class S73_Mid_48_旋转图像 {

    /**
     * .S73_Mid_48_旋转图像
     * .<p>
     * .LeetCode题目链接：<a href="https://leetcode.cn/problems/rotate-image/">https://leetcode.cn/problems/rotate-image/</a>
     * .<p>
     * .给定一个 n × n 的二维矩阵 matrix 表示一个图像，请你将图像顺时针旋转 90 度。要求必须 原地(in-place) 旋转，
     * .即直接修改输入矩阵，不允许申请另一个等大小的矩阵进行拷贝后再写回（空间复杂度需为 O(1)）。
     * .<p>
     * .示例：
     * .1) 输入：[[1,2,3],[4,5,6],[7,8,9]]  输出：[[7,4,1],[8,5,2],[9,6,3]]
     * .2) 输入：[[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
     * .3) 输入：[[1]] 输出：[[1]]
     * .<p>
     * .标签：数组(Array) / 矩阵(Matrix) / 原地算法(In-place) / 模拟(Simulation)
     * .<p>
     * .常见的两种在 O(1) 额外空间完成顺时针旋转 90° 的思路：
     * .1. "翻转两次法"：先做 垂直方向翻转(上下对称) 或 水平方向翻转(左右对称)，再进行 主对角线(左上到右下) 或 副对角线(右上到左下) 的转置。
     * .   组合中满足最终顺时针效果的一种是：先垂直翻转(上下互换)，再沿主对角线转置；或先水平翻转，再沿副对角线转置。
     * .   本实现采用：先垂直翻转(上下对换)，再主对角线转置。
     * .2. "四点循环置换(layer-by-layer)"：按从外到内的环(layer)遍历，每次把四个位置的元素进行循环交换，实现局部旋转。
     * .<p>
     * .为什么 "翻转两次法" 可行？
     * .设一个坐标 (r, c) 在 n×n 矩阵中：
     * .顺时针旋转后的坐标应该变到 (c, n - 1 - r)。
     * .先做垂直翻转： (r, c) -> (n - 1 - r, c)
     * .再做主对角线转置： (n - 1 - r, c) -> (c, n - 1 - r) 正是目标位置。
     * .<p>
     * .ASCII 图解 (以 3×3 为例)：
     * .原始：        垂直翻转：      主对角线转置(完成)：
     * .1 2 3        7 8 9         7 4 1
     * .4 5 6   ->   4 5 6   ->    8 5 2
     * .7 8 9        1 2 3         9 6 3
     * .<p>
     * .Layer 四点循环置换原理 (示意以最外层四个角)：
     * .top-left -> top-right -> bottom-right -> bottom-left -> 回 top-left
     * .每个环内对每个偏移 offset 做一次 4 元素轮换。
     * .<p>
     * .复杂度分析：
     * .时间复杂度：O(n^2) — 需要访问每个元素常数次。
     * .空间复杂度：O(1) — 只使用有限的临时变量。
     * .<p>
     * .关键洞察：
     * .- 旋转是一个坐标映射问题，可通过分解为两次可逆的简单操作（翻转 + 转置）达到目的。
     * .- 任意 n×n 矩阵顺时针 90° 的映射公式 (r, c) -> (c, n - 1 - r) 可以被两步简单操作组合得到。
     * .- 如果不熟悉坐标公式，layer 循环交换法更具“操作感”，但翻转+转置更简洁好写且不易出错。
     */
    public void rotate(int[][] matrix) {
        int size = matrix.length; // n × n 的维度
        // 边界条件：0 或 1 直接返回
        if (size <= 1) {
            return;
        }
        // 第一步：垂直翻转（上下行交换） - 将第 row 行与倒数第 row 行交换
        for (int topRow = 0; topRow < size / 2; ++topRow) {
            int bottomRow = size - 1 - topRow;
            for (int col = 0; col < size; ++col) {
                int temp = matrix[topRow][col];
                matrix[topRow][col] = matrix[bottomRow][col];
                matrix[bottomRow][col] = temp;
            }
        }
        // 第二步：沿主对角线转置（行列互换） - 只需在上三角区域进行交换防止重复
        for (int row = 0; row < size; ++row) {
            for (int col = 0; col < row; ++col) { // col < row 保证只遍历下三角或上三角的一半
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }
    }

    /**
     * .备选方案：layer-by-layer 四点循环置换法。
     * .每一层(layer)定义：从当前边界 left/top 到 right/bottom。
     * .对于每个 layer 内的偏移 offset：进行 4 元素的轮换。
     * .更直观但代码稍长，可用于对比理解。
     */
    public void rotateByLayer(int[][] matrix) {
        int n = matrix.length;
        if (n <= 1) {
            return;
        }
        // 只需要处理前 n/2 层（向内收缩）
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;            // 当前层的起始索引
            int last = n - 1 - layer;     // 当前层的结束索引
            for (int offset = 0; offset < last - first; offset++) {
                int top = first;          // 顶行固定为 first
                int bottom = last;        // 底行固定为 last
                int left = first + offset;
                int right = last - offset;
                // 四点轮换 (top-left -> top-right -> bottom-right -> bottom-left -> back)
                int topLeftVal = matrix[top][left];
                // bottom-left -> top-left
                matrix[top][left] = matrix[bottom - offset][first];
                // bottom-right -> bottom-left
                matrix[bottom - offset][first] = matrix[bottom][right];
                // top-right -> bottom-right
                matrix[bottom][right] = matrix[top + offset][last];
                // 保存的 top-left -> top-right
                matrix[top + offset][last] = topLeftVal;
            }
        }
    }

    // 工具方法：打印矩阵，便于调试与展示
    private static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            StringBuilder sb = new StringBuilder();
            for (int val : row) {
                sb.append(val).append(" ");
            }
            System.out.println(sb.toString().trim());
        }
    }

    // 工具方法：深拷贝一个矩阵（便于测试两个不同实现的结果是否一致）
    private static int[][] copyMatrix(int[][] original) {
        int n = original.length;
        int[][] clone = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(original[i], 0, clone[i], 0, n);
        }
        return clone;
    }

    // 工具方法：比较两个矩阵是否相等
    private static boolean equalMatrix(int[][] a, int[][] b) {
        if (a.length != b.length) return false;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] != b[i][j]) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        S73_Mid_48_旋转图像 solution = new S73_Mid_48_旋转图像();
        System.out.println("=== 旋转图像 测试开始 ===\n");

        // 测试1：题目示例 3×3
        int[][] case1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[][] expected1 = {{7, 4, 1}, {8, 5, 2}, {9, 6, 3}};
        runTest("示例1 3×3", solution, case1, expected1);

        // 测试2：题目示例 4×4
        int[][] case2 = {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}};
        int[][] expected2 = {{15, 13, 2, 5}, {14, 3, 4, 1}, {12, 6, 8, 9}, {16, 7, 10, 11}};
        runTest("示例2 4×4", solution, case2, expected2);

        // 测试3：1×1 边界
        int[][] case3 = {{42}};
        int[][] expected3 = {{42}};
        runTest("边界 1×1", solution, case3, expected3);

        // 测试4：2×2 最小非平凡尺寸
        int[][] case4 = {{1, 2}, {3, 4}};
        int[][] expected4 = {{3, 1}, {4, 2}};
        runTest("基本 2×2", solution, case4, expected4);

        // 测试5：5×5 自定义矩阵
        int[][] case5 = {
                {1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20},
                {21, 22, 23, 24, 25}
        };
        int[][] expected5 = {
                {21, 16, 11, 6, 1},
                {22, 17, 12, 7, 2},
                {23, 18, 13, 8, 3},
                {24, 19, 14, 9, 4},
                {25, 20, 15, 10, 5}
        };
        runTest("扩展 5×5", solution, case5, expected5);

        // 测试6：验证两种实现一致性 (3×3)
        System.out.println("\n--- 测试6：验证 rotate 与 rotateByLayer 结果一致 (3×3) ---");
        int[][] original = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[][] copy1 = copyMatrix(original);
        int[][] copy2 = copyMatrix(original);
        solution.rotate(copy1);
        solution.rotateByLayer(copy2);
        System.out.println("rotate 结果：");
        printMatrix(copy1);
        System.out.println("rotateByLayer 结果：");
        printMatrix(copy2);
        assert equalMatrix(copy1, copy2) : "两种方法结果应该一致";
        System.out.println("✓ 两种实现结果一致\n");

        // 测试7：随机矩阵（简单可读）
        System.out.println("--- 测试7：自定义 4×4 验证一致性 ---");
        int[][] random4 = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        int[][] r1 = copyMatrix(random4);
        int[][] r2 = copyMatrix(random4);
        solution.rotate(r1);
        solution.rotateByLayer(r2);
        assert equalMatrix(r1, r2) : "随机4×4矩阵两种方法结果必须一致";
        System.out.println("✓ 随机4×4一致性测试通过\n");

        System.out.println("=== 所有测试完成 ===");
    }

    private static void runTest(String title, S73_Mid_48_旋转图像 solution, int[][] input, int[][] expected) {
        System.out.println("--- " + title + " ---");
        System.out.println("原矩阵：");
        printMatrix(input);
        int[][] working = copyMatrix(input); // 保留原始显示
        solution.rotate(working);
        System.out.println("旋转后：");
        printMatrix(working);
        boolean ok = equalMatrix(working, expected);
        System.out.println("期望：");
        printMatrix(expected);
        System.out.println("结果校验：" + (ok ? "通过" : "失败"));
        assert ok : title + " 测试未通过";
        System.out.println("✓ 测试通过\n");
    }
}
